#include <iostream>
#include "insertionSort2.h"

/**
 * 在含有大量重复元素时效率最高
 * 三路快排 arr[l...r],将其分为 <v, =v, >v 三部分
 * 递归对 <v, >v 两部分三路快排
 *
 */
template<typename T>
void __quickSort3Ways(T arr[], int l, int r){
	if(r - l <= 15){
		insertionSort2(arr, l, r);
		return;
	}
	// partition
	swap(arr[l], arr[rand()%(r-l+1) + l]);

	T v = arr[l];

	int lt = l;		// arr[l+1...lt] < v 初始为空
	int gt = r + 1;	// arr[gt...r] > v
	int i = l + 1;	// arr[lt+1...i) == v

	while(i < gt){
		if(arr[i] < v){
			swap(arr[i], arr[lt + 1]);
			lt++;
			i++;
		}else if(arr[i] > v){
			swap(arr[i], arr[gt - 1]);
			gt--;
		}else{		// arr[i] == v
			i++;
		}
	}
	swap(arr[l], arr[lt]);

	__quickSort3Ways(arr, l, lt - 1);
	__quickSort3Ways(arr, gt, r);
}

template<typename T>
void quickSort3Ways(T arr[], int n){
	srand(time(NULL));
	__quickSort3Ways(arr, 0 ,n - 1);
}
